/* 两数之和
1.  暴力法:双指针
思路及算法
最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。
当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

2.  哈希表法
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int * returnSize) /* int* returnSize为返回值的个数（这个不可以省略）*/
{
    int *array = (int *)malloc(sizeof(int) * 2);/* 开辟空间来存储下标*/
    for (int idx = 0; idx < numsSize; idx++)
    {
        for (int jdx = idx + 1; jdx < numsSize; jdx++)/* 内层循环从idx + 1 开始，避免反向获取*/
        {
            if (nums[idx] + nums[jdx] == target)
            {
                /* 返回这两个元素的下标*/
                array[0] = idx;
                array[1] = jdx;
                *returnSize = 2;
                return array;/* 返回下标*/
            }
        }
    }
    return NULL;


}

int main()
{
    /* malloc使用后free释放
    在使用完malloc函数后

    需要用free函数来释放malloc创建的内存空间
    需要将创建的指针变量指向空指针，以防程序错误调用*/
    int nums[] = {2, 7, 11, 19};
    int target = 18;
    int returnSize = -1;
    int len = sizeof(nums) / sizeof(int);
    int* a = twoSum(nums, len, target, &returnSize);
    for (int idx = 0; idx < 2; idx++)
    {
        printf("%d\n", a[idx]);
    }
    return 0;
}